package everydayone.majorityelement;
/**
 * @Date 2020/03/13
 * @author 王光浩
 * @Thinking 使用投票法。（就好比大选一样，由于有超过一半的众数，所以投票的结果一定时选出众数）
 * @Analysis 时间复杂度O（n），空间复杂度O（1）
 */
public class MethodThree {
	public int majorityElement(int[] nums) {
		int candidate=0;
		int count=0;
		for(int i:nums) {
			if(count==0)
				candidate=i;
			count=(candidate==i)?(count+1):(count-1);
		}
		return candidate;
	}
}
